class TreeNode(object):
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

# 递归
# class Solution(object):
#     def constructMaximumBinaryTree(self, nums):
#         """
#         :type nums: List[int]
#         :rtype: TreeNode
#         """
#         if not nums:
#             return None
#         max_value = max(nums)
#         max_index = nums.index(max_value)
#         node = TreeNode(max_value, self.constructMaximumBinaryTree(nums[:max_index]),
#                         self.constructMaximumBinaryTree(nums[max_index + 1:]))
#         return node

# 单调栈
class Solution(object):
    def constructMaximumBinaryTree(self, nums):
        """
        :type nums: List[int]
        :rtype: TreeNode
        """
        node = TreeNode(nums[0])
        stack = [node]
        for num in nums[1:]:
            node = TreeNode(num)
            if num < stack[-1].val:
                stack.append(node)
            else:
                while len(stack) > 1 and num > stack[-2].val:
                    last_node = stack.pop()
                    stack[-1].right = last_node
                last_node = stack.pop()
                node.left = last_node
                stack.append(node)
        while stack:
            node = stack.pop()
            if stack:
                stack[-1].right = node
        return node


